package com.yusong.algorithm.array;

import java.util.Arrays;

/**
 * 快速排序
 * 快速排序找到指定元素的位置
 * 应该采用堆排序(优先队列）
 */
public class PartitionSort215 {

    public static void main(String[] args) {
        int[] grid = {3,2,1,5,6,4};

        PartitionSort215 main = new PartitionSort215();

        int result = main.findKthLargest(grid,2);

        System.out.println(Arrays.toString(grid));

        System.out.println(result);
    }


    public int findKthLargest(int[] nums, int k) {
        int length = nums.length;
        int right = length;
        int left = 0;
        while (left < right){

            int position = partition(left,right,left, nums);
            if(position == length -k) {
                return nums[position];
            }else if(position > length -k){
                right = position;
            }else {
                /*int next = position+1;
                while (nums[next] == nums[position]){
                    if(next == length -k){
                        return nums[next];
                    }
                    next++;
                }*/
                left = position +1;
            }

        }

        return -1;
    }


    /**
     * 快排核心
     * 分区找到指定元素的位置，右边更大，左边更小
     * 右闭合，左边开
     */
    private int partition(int left, int right,int index, int[] nums){
        int indexValue = nums[index];
        for(int i=left; i < right; ){
            int thisValue = nums[i];
            if(thisValue == indexValue){
                i++;
            }else if(thisValue > indexValue){
                right --;
                switchNum(nums, i, right);
            }else {
                switchNum(nums, i, left);
                left++;
                i++;
            }
        }
        return left;
    }



    private void switchNum(int[] nums,int m, int n){
        int temple = nums[m];
        nums[m] = nums[n];
        nums[n] = temple;
    }



}
/**
 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 输入: [3,2,1,5,6,4] 和 k = 2
 输出: 5
 */
